T=20;
n=[92,93,95,100,95,96,93,91,93,96,93,98,95,97,93,98,93,99,95,100];
a=[9818,2216,13014,10214,9213,15618,7412,5617,1814,6220,13216,14212,11814,8413,2019,6616,14021,13620,6020,13817,4414,6817,17015,8620,5820,5014,16217,16818,8817,10420,14821,12218,7817,17215,17418,3616,15413,3819,5216,4815,10812,14415,16012,11017,19017,1619,3413,2620,18617,18417,11614,4616,15014,13413,14621,11220,2420,7613,4212,17819,16415,15217,12421,18012,2820,8219,1218,12619,9019,12014,3019,19217,5418,9621,1417,16612,8015,7216,4015,10620,10016,3221,6414,12813,18216,18821,1017,17613,15816,11412,9412,7016,3334,8746,16547,2538,6346,10143,13942,4747,1535,4142,9547,11333,8346,19748,6148,2937,12532,14942,16338,18346,18136,19151,5950,12943,5340,12333,4541,17341,18549,14740,7551,9747,6745,15151,13135,7945,3536,13745,15947,3944,1932,10946,2134,14334,5545,11946,7147,16932,17545,12739,11734,3133,6540,7340,4333,10734,9149,6948,8939,18743,12142,3736,16148,9948,15532,14135,13342,1749,11535,5736,15334,9338,19338,1332,17743,5144,2336,19533,15741,10334,18951,14535,11143,8136,16741,4932,17939,13548,8541,7749,10541,17146,2743,20020,20225,2419,11019,4223,8622,5622,18820,17821,7623,19221,13621,7025,15422,18224,8020,9021,13422,9419,6419,17220,3023,17023,2624,15622,5224,20423,16820,19423,11621,16021,8823,18619,14822,2224,4425,7224,20622,7825,5024,4824,10022,15823,5820,16220,17422,11223,19825,15023,3421,10223,19019,12823,2024,8423,4619,9224,16424,5424,10823,10421,4025,9621,10624,18422,9824,14025,19625,3621,13221,11824,14224,13821,12020,3820,2825,11423,8221,6019,16622,7424,13024,6619,3223,14421,6219,14620,12222,15225,1823,17624,6820,18022,12619,12425,15648,20449,12649,18050,9651,19848,6451,5851,6248,16651,19050,13048,17049,21052,18848,10849,15449,8048,21251,10047,5247,17448,1651,9252,8848,8648,19247,4851,20649,7648,16847,10648,20251,16052,18650,14252,17252,19651,18452,13250,15848,3849,2050,14850,10248,19448,11051,9847,6847,2851,20048,9051,9449,13650,10448,4250,12250,16251,17651,11849,12051,18247,4052,12447,7850,20852,5449,3648,7452,2251,8447,2447,8249,6049,11249,13448,1852,11651,1450,17851,3452,7049,6651,2647,12849,3247,11447,16449,14050,4448,7247,13848,14648,15050,5052,14450,3048,15249,5652,4651,10544,9145,5144,8342,5744,12743,20542,14142,6343,9542,11345,8542,15143,17545,17742,12542,18342,4543,8743,2744,9742,5544,4743,2342,6145,15945,10743,19544,17343,4945,18145,17945,16944,7342,7544,19144,8944,10943,19743,14542,16144,9944,11145,12945,17144,14345,16543,19342,13145,12345,15342,16342,5343,14742,20344,15545,2542,13945,3944,2145,3542,18944,5945,10143,1943,19944,4143,11543,3343,20143,6945,7745,15742,2943,13344,12143,18543,18745,7144,20743,3144,11745,6745,4342,7943,11945,16744,8143,9343,3742,14943,13544,10342,6544,13742,3454,11054,7454,11854,6254,20254,9054,20454,11454,7854,17654,16254,10854,19654,3254,15854,13054,8654,6654,5454,20054,4854,8254,12854,15054,13454,14054,9454,14654,17054,9254,14854,19854,5854,4054,8854,1654,4654,19454,2854,15254,16054,5254,12054,10054,3654,14254,3054,18654,18854,17854,18254,7254,16454,2054,5054,16854,17254,9654,9854,4254,8454,1454,13854,13654,12454,10654,3854,5654,16654,12654,11654,2254,6054,15654,7054,19254,13254,18054,7654,6854,2654,4454,8054,6454,1854,14454,18454,10454,19054,2454,17454,11254,15454,10254,12254,10500,10891,17104,19697,18706,13100,11091,20102,12899,18492,3692,5303,19091,2306,9501,9105,11496,4500,18101,6103,17295,11300,14304,11700,16697,18295,7499,16503,8900,17503,6701,14899,19904,6494,1900,10101,7095,13506,2091,5106,8692,3297,5501,18896,10704,12700,13896,4701,13300,9700,15301,20304,8297,16903,15694,5892,19306,2897,7700,12105,14692,2506,11897,6895,12497,10297,4101,7303,3495,14096,15895,12298,9301,17900,9902,13702,14500,7899,4306,3098,15494,8101,6297,16096,4900,2700,3906,5692,19506,16293,17692,8492,15092,10048,13842,12441,18643,5840,14044,9441,8847,13052,16252,10845,2242,14437,16842,13645,17850,9042,18041,14843,17447,18246,12252,3840,18849,15842,6449,4449,13440,16651,8639,2649,7451,11246,19242,8247,11041,1238,5253,1849,14241,4041,2441,9651,11440,10238,2041,17248,7643,10448,1444,15448,18448,16450,15651,4840,9245,15051,6641,6845,17653,10654,13254,9843,7239,15245,3251,4647,8046,3443,12052,5049,2839,7842,11651,6247,16047,6042,4246,12638,5642,3637,7051,12850,5452,14643,3054,1640,8446,11840,19038,17040,11112,2122,5919,17512,14718,18717,3317,11516,18110,9308,4720,3518,7123,13314,6720,17709,18516,12719,19518,2710,8307,14118,9513,4507,7519,12307,13917,6308,1716,9912,8115,17113,5108,5712,7309,3913,17919,14507,14314,13121,8915,15322,3708,15118,16721,10709,11721,15710,16123,12516,19919,15522,6509,12914,19314,8513,19713,2514,4312,13523,6108,10120,16907,18322,8716,9118,4117,16317,15915,10312,11313,3121,5318,9713,1916,6915,7920,19108,4921,11913,13717,12113,2918,20112,7712,18922,5518,2310,10910,14919,10513,16510,17307,10707,6110,16310,13908,15309,17111,3708,1510,12109,11712,10312,17910,3511,4912,11507,6710,9711,5908,17511,15507,13508,11310,8110,8708,18510,19508,4709,5508,12510,6908,16507,1308,5310,19311,10507,18712,9311,7308,8511,14711,14112,4312,14511,1110,9912,2307,15710,19112,19912,10911,16908,9509,15109,2108,7912,20110,13112,12907,10107,11909,19712,2510,15912,7112,11112,2908,1910,6509,18910,16710,16107,5709,2710,9107,17708,4110,4510,12307,3309,3112,8307,14910,5112,6309,12711,14312,13712,8911,18312,18110,13310,1708,7510,3910,7710,17308,15157,7559,16161,19756,13755,18560,9960,11954,8961,8761,4156,17558,9353,6159,18954,7758,12353,8157,3359,11554,14758,6755,5555,19553,15956,11157,3756,13956,20158,1961,12755,16957,5961,1761,13155,6354,18156,10757,13361,17154,7161,16557,2756,5160,14554,10553,18756,14957,10954,10158,19955,14357,17954,12956,4353,6558,19161,11357,2955,9553,16757,8556,4559,4760,4957,17756,2557,9759,15760,17359,15359,12554,11753,14161,8358,7359,5354,12154,6953,2158,3560,16361,19356,13558,15559,3159,2354,9154,5754,7954,3961,10360,18358,10178,7970,11576,9384,20168,5983,17382,10370,8784,12973,9172,20382,9779,11175,17180,3178,13566,14965,19184,6382,14368,18784,2971,3576,7781,18578,8578,1978,17770,3975,10566,4577,6567,18171,14174,3367,10766,14765,6970,16773,12565,15767,6780,13170,12770,18367,10966,19982,15170,7572,4772,17969,9973,20979,8370,14578,19568,12373,1783,1572,2384,11378,16369,5578,5774,12184,19784,6169,13379,19376,8965,2576,16174,16975,9566,17584,4375,15581,20584,13965,3778,5167,2169,18974,7183,7374,4165,11776,8169,13774,4974,15371,15972,11980,16572,2771,5371,20775,5286,10887,15088,17886,7087,6288,8889,19287,2889,14687,18687,12686,15487,18486,2487,4487,9286,19888,6488,3686,9087,19088,18086,16489,15687,10486,7689,11887,8687,3088,14087,17487,20289,2687,9687,3287,17286,7889,8487,12889,7288,5689,19488,15286,11287,19689,10086,13086,5887,16888,10686,9889,2086,1889,11086,15888,6089,16689,10289,16287,4886,18287,13287,3889,13488,6887,2286,3486,12086,5489,13888,8287,1489,9488,14888,11487,17089,8088,4289,1689,11689,17689,7486,12286,14488,16086,20088,14289,18889,12487,4687,6689,5086,13689,4089,2091,5490,19689,6297,16302,5291,8101,4486,4691,10494,8298,17687,7097,12698,17096,7900,1690,19489,7490,14890,2494,12092,8694,7687,8503,4089,4303,6699,17299,11303,10903,6890,13696,10296,14694,9094,15692,9886,19099,9298,1896,3290,11896,18298,16904,5093,11704,10699,8893,15891,7300,1304,20495,9502,12888,2692,17893,5894,19898,20293,15097,1498,6087,12491,4904,14300,3100,20094,16498,3693,16686,10093,18494,18895,3493,16102,2287,3894,14097,13297,17490,13486,11489,9696,18097,15497,13086,2899,19295,6496,11103,12302,14491,13894,18697,15294,5704,2515,9515,1917,16915,4317,13915,4516,10715,12717,10515,15116,1716,11716,2715,14116,2916,10315,7116,11316,16116,15915,9716,8916,17117,13717,19515,5516,5717,10115,16317,16715,11116,1316,9915,3717,15715,16515,3515,6317,7916,14715,14317,6516,13117,7516,7317,18715,5917,3916,4115,2316,17716,6117,9315,8516,1115,8715,12917,5117,8115,3117,6915,12117,10917,11516,18315,2116,1516,19116,6716,18915,17517,8316,12315,14917,9117,11915,13516,15516,19315,13315,18516,7717,4717,3317,5316,18116,14517,17916,12515,15316,4915,17315,11337,15735,5337,3135,18137,9335,6537,5134,2537,14334,4134,4334,6335,15534,19734,7336,7737,6734,15134,14136,12935,5936,13534,3936,4735,19537,18737,12136,1935,11934,19135,2134,8135,15334,20135,4535,16934,1735,3337,12735,9735,18934,9936,9136,7937,17934,10337,13136,2737,1534,13337,16536,8535,11536,18537,19337,7536,12535,18334,20537,8737,5737,20734,16336,5535,20936,14935,10936,17335,6937,14737,8935,3534,10735,14537,16134,13735,19936,17536,16735,9535,15937,2336,2937,17136,20334,4934,10135,11737,10536,3737,13937,6134,17736,8336,7137,12334,11134,17858,16057,17458,2857,4457,4057,2458,18857,6258,11257,14858,2058,19657,14258,3058,19858,10257,16657,7258,11858,15257,12858,3458,9658,15458,17658,3857,6858,13857,18057,9058,8458,11057,19058,5457,15058,12258,8657,16857,13458,15857,6057,8058,17058,13257,4658,6658,12057,10457,10657,3658,9457,11657,4857,11458,12657,9257,19257,5258,14058,5657,5858,18657,7058,17257,16258,13658,10057,14657,1657,16458,7457,18458,4257,10858,5057,1457,8857,2258,14457,7857,1858,12458,8257,2657,9858,18257,13057,7657,6458,3258,15658,19458,14319,16315,7919,10920,15117,14518,10114,14715,11720,16517,8315,12914,16117,7124,17724,9521,2518,3113,12519,4321,15319,6521,3317,4522,5724,11520,4715,1524,10316,17124,9922,17315,20719,10516,12720,14118,15723,17524,3519,20313,13323,4921,18124,20517,5317,17920,7716,7323,1915,11319,18313,16715,18920,6317,15918,18719,8521,2715,5517,2915,13722,19915,5923,6121,6919,11916,14920,12313,2118,6714,18516,9313,2313,7521,3921,1717,9719,8123,10720,12115,3713,19116,8916,15523,9123,13121,21119,20116,4124,8715,16921,19515,13516,11113,13918,20918,19724,19320,5114,13480,8279,16280,7887,8684,6882,8483,2078,14077,7279,9881,11679,11885,6678,18683,9083,8880,12477,6479,13685,15678,5686,14678,16685,7485,12281,2678,4283,4680,15084,17484,1482,2487,18483,19677,3677,10880,14484,1681,6083,17679,10483,15483,5286,13085,5083,4484,1883,14885,11281,11482,16486,1084,7680,1285,13887,9677,17085,11087,16879,14278,5478,3877,12682,17886,16079,2882,12082,12877,6278,19279,10086,8082,18883,15280,3083,2287,10678,3486,17283,19486,5881,19086,4077,19885,18281,15880,9284,7085,18080,4883,9487,13286,10281,3280,18442,20229,5631,11229,5431,4630,19839,11434,5831,6431,4841,19235,4433,19036,10231,17830,21038,8837,16837,16429,1633,17627,14042,19627,6039,3431,13039,3235,6837,18227,10039,2831,10442,20627,10837,7841,13232,18636,16230,17434,12440,8241,4232,12228,5234,12031,15232,8636,1234,3631,11635,8033,2439,18834,13430,13641,1439,8433,7027,20839,14641,12638,11033,17228,3829,9028,2642,9839,20042,2037,9236,13832,4042,15642,7230,14230,17037,1828,5038,12839,15842,14429,10635,2227,15438,16628,18031,7439,20437,9637,6235,14838,15041,7635,3041,16035,11833,6628,9440,19437];